package com.leetcode.offer;

/**
 * @author zfl
 * @Classname FIB
 * @Description 斐波那契数列
 * @Date 2020/10/13 14:40
 */
public class Fib {

    /**
     * @param n
     * @return
     * 递归法 时间复杂度O(2^n)
     * 空间复杂度 O(n)
     */
    public static int fib1(int n) {
        if(n == 0) {
            return 0;
        }
        if(n == 1) {
            return 1;
        }

        return (fib1(n - 1) + fib1(n - 2)) % 1000000007;
    }

    /**
     * @param n
     * @return
     * 动态规划法
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：35.4 MB, 在所有 Java 提交中击败了74.57%的用户
     */
    public static int fib2(int n) {
        int a = 0,b = 1, sum = 0;
        for (int i = 0; i < n; i++) {
            sum = (a + b) % 1000000007;
            a = b;
            b = sum;
        }
        return a;

    }
}
